//二分查找适用于有序数组
//常见的查找区间是左闭右开和左闭右闭
//使用二分查找时要定好查找区间，确定好原则




//左闭的性质是由整数除法向下取整决定的
#include<vector>
using std::vector;
//第一种是左闭右闭
int bSearch_Rb(vector<int>& nums,int target)
{
    int right=nums.size()-1;    //右闭，需要搜索index为size()-1
    int left=0;
    while(left<=right)   //按区间定义来，l=r时候区间有定义，使用<=
    {
        int middle=(left+right)/2;
        if(nums[middle]==target)    
            return middle;
        else if(nums[middle]>target)    //target在left和middle之间
            right=middle-1;     //这里是主要区别，闭区间时，middle所在的一定不是target，不搜索，所以区间不包括middle
        else
            left=middle+1;
    }
    return -1;
}

//左闭右开区间
int bSearch_Rk(vector<int>& nums,int target)
{
    int right=nums.size();  //不包括nums.size()，但是右开
    int left=0;
    while(left<right)   //相等时区间无意义
    {
        int middle=(right+left)/2;
        if(nums[middle]==target) 
            return middle;
        else if(nums[middle]>target)
            right=middle;   //闭区间，要包括middle-1的元素，所以设置right为middle，并不会访问middle
        else
            left=middle+1;
    }
    return -1;
}
